package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {100, 250, 5, 6, 5, 85, 24, 14, 10, 52, 30, 15, 34, 64};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    /*
        1. 用left和right标出处理范围，最初从0到length-1范围进行处理
        2. 选取第一个值作为基准值
        3. 下标i和j，分别从left和right开始
        4. j循环向左移动，如果找到>=基准值的值，继续向左，否则停下
        5. j位置找到的小值，踢到i位置
        6. i循环向右移动，如果找到<=基准值的值，继续向右，否则停下
        7. i位置找到的大值，踢到j位置
        8. i和j重合时，循环停止
        9. 基准值放入i位置
        10. 递归处理左侧的 left到i-1 范围
        11. 递归处理右侧的 i+1到right 范围

        最简问题：一个值（left和right重合），没有值（left>right）
     */

    //快速排序
    private static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int left, int right) {
        if (left >= right) { //最简问题，递归结束的条件
            return;
        }
        int base = a[left]; //以第一个元素为左侧做个基准值进行参照
        int i = left; //i下标为起始位置
        int j = right; //j下标为末尾的位置
        while (i < j) { //i,j不重合就继续执行
            while (i < j && a[j] >= base) { //当右侧下标的值>=基准值，就将该值往前推
                j--;
            }
            a[i] = a[j];
            while (i < j && a[i] <= base) { //当左侧下标的值<=基准值，就将该值往后移
                i++;
            }
            a[j] = a[i]; //i的位置与j的位置进行交换
        }
        a[i] = base; //循环结束后将base的值赋给a[i]，就是将基准值还原为a[left]
        sort(a, left, i - 1); //递归将数组的元素移动到基准值的左侧
        sort(a, i + 1, right); //递归将数组的元素移动到基准值的右侧
    }
}
